#include<bits/stdc++.h>

using namespace std;
//文法：E->E+T|T     T->T*F|F     F->(E)|i
//根据预测分析表M[A，a]对输入串进行自上而下的语法分析程序
//已知预测分析表M[A，a]和输入串
//判别输入串是否为文法的句子，并生成预测分析步骤


char Vn[] = {'E', 'e', 'T', 't', 'F'};      //定义文法的非终结符，小写字母e表示E’
char Vt[] = {'i', '+', '*', '(', ')', '#'};  //定义文法的终结符
int LENVt = sizeof(Vt);

void showstack(stack<char> st)       //从栈底开始显示栈中的内容
{
    int i, j;
    char ch[100];
    j = st.size();
    for (i = 0; i < j; i++) {
        ch[i] = st.top();
        st.pop();
    }
    for (i = j - 1; i >= 0; i--) {
        cout << ch[i];
        st.push(ch[i]);
    }
}

int find(char c, char array[], int n)                     //查找函数，返回布尔值
{
    int i;
    int flag = 0;
    for (i = 0; i < n; i++) {
        if (c == array[i])
            flag = 1;
    }
    return flag;
}

int location(char c, char array[])         //定位函数,指出字符所在位置，即将字母转换为数组下标值
{
    int i;
    for (i = 0; c != array[i]; i++);
    return i;
}

void error() {
    cout << "                    出错!" << endl;
}

void analyse(char Vn[], char Vt[], string M[5][6], string str) {
    int i, j, p, q, h, flag = 1;
    char a, X;
    stack<char> st;                 //定义堆栈
    st.push('#');
    st.push(Vn[0]);                  //#与识别符号入栈
    j = 0;                             //j指向输入串的指针
    h = 1;
    a = str[j];
    cout << "步骤            " << "分析栈                " << "剩余输入串           " << " 所用产生式" << endl;
    while (flag == 1) {
        cout << h << "                ";                    //显示步骤
        h++;
        showstack(st);                                   //显示分析栈中内容
        cout << "                      ";
        for (i = j; i < str.size(); i++) cout << str[i];          //显示剩余字符串
        X = st.top();                                      //取栈顶符号放入X
        if (find(X, Vt, LENVt) == 1)                          //X是终结符
            if (X == a)                              //分析栈的栈顶元素和剩余输入串的第一个元素相比较
                if (X != '#') {
                    cout << "                   " << X << "匹配" << endl;
                    st.pop();
                    a = str[++j];                //读入输入串的下一字符
                } else {
                    cout << "                    " << "接受!" << endl << endl;
                    flag = 0;
                }
            else {
                error();
                break;
            }
        else {
            p = location(X, Vn);             //实现下标的转换（非终结符转换为行下标）
            q = location(a, Vt);             //实现下标的转换（终结符转换为列下标）
            string S1("NULL"), S2("null");
            if (M[p][q] == S1 || M[p][q] == S2)      //查找二维数组中的产生式
            {
                error();
                break;
            }   //对应项为空，则出错
            else {
                string str0 = M[p][q];
                cout << "                  " << X << "-->" << str0 << endl; //显示对应的产生式
                st.pop();
                if (str0 != "$")        //$代表“空”字符
                    for (i = str0.size() - 1; i >= 0; i--) st.push(str0[i]);//产生式右端逆序进栈
            }
        }
    }
}


int main() {
    string M[5][6] = {"Te", "NULL", "NULL", "Te", "NULL", "NULL",
                      "NULL", "+Te", "NULL", "NULL", "$", "$",
                      "Ft", "NULL", "NULL", "Ft", "NULL", "NULL",
                      "NULL", "$", "*Ft", "NULL", "$", "$",
                      "i", "NULL", "NULL", "(E)", "NULL", "NULL"};  //预测分析表j
    string str;
    int errflag, i;
    cout << "文法：E->E+T|T     T->T*F|F     F->(E)|i" << endl;
    cout << "请输入分析串（以#结束）：" << endl;
    do {
        errflag = 0;
        cin >> str;
        for (i = 0; i < str.size(); i++)
            if (!find(str[i], Vt, LENVt)) {
                cout << "输入串中包含有非终结符" << str[i] << "(输入错误)!" << endl;
                errflag = 1;
            }
    } while (errflag == 1); //判断输入串的合法性
    analyse(Vn, Vt, M, str);
    return 0;
}
